/**
 * Heap
 * An implementation of a Binomial Heap with non-negative integer
 * values.
 * Submitted by:
 * Noam Mor, username: noammor, ID: 300094836
 * Hila Peleg, username: hilapel1, ID: 200167591
 *
 */
public class Heap
{
	/**
	 * The pointer to thehead of the linked list of the trees that
	 * make up the heap.
	 */
	private HeapNode rootListHead = null;
	/**
	 * A pointer to the root of the tree holding the minimum, which is
	 * the minimum node of the heap. This is to make finding the minimum
	 * O(1).
	 */
	private HeapNode minimum = null;
	/**
	 * The size of the heap.
	 */
	private int size = 0;
	/**
	 * public boolean empty()
	 *
	 * precondition: none
	 * 
	 * The method returns true if and only if the heap
	 * is empty.
	 * Retuns true if there are no trees in the heap.
	 * Complexity: A single pointer comparison - O(1)
	 *   
	 */
	public boolean empty(){
    	return (rootListHead == null);
    }
		
	/**
     * public int getHeapsize()
     *
     * precondition: none
     * 
     * The method returns the number of elements in the 
     * heap.
     * Returns the size member of the class, runs at O(1).
     *   
     */
	public int getHeapsize(){
    	return size;
    }
    
	/**
     * public boolean isHeap()
     *
     * precondition: none
     * 
     * The method returns true if and only if the heap
     * satisfies the heap property or heapsize==0.
     * 
     * This method iterates over all tree roots in the linked list
     * and calls the recursive isHeap() method of HeapNode for each
     * of them. If any of them returns false, it will stop and return
     * false.
     *
     * Complexity: Let us assume the n elements of the heap are divided into
     * k trees sized n_1 + n_2 + ... + n_k = n.
     * For each of the k trees, HeapNode's isHeap will be called at O(n_i).
     * For the worst case, in which the element is not found, the iteration will
     * run all k trees at O(n_1 + n_2 + ... + n_k) = O(n).  
     */
    public boolean isHeap() 
    {
    	HeapNode node = rootListHead;
    	
    	while (node != null) {
    		if (!node.isHeap()) {
    			return false;
    		}
    		node = node.nextSibling;
    	}
    	return true;
    	
    }

    /**
    * public void insert(int value)
    *
    * precondition: value >= 0
    *               isHeap()
    * 
    * postcondition: isHeap()
    * Inserts a new value into the heap, by creating a new HeapNode,
    * which is equivilent to a heap with only one element, when
    * examining only its trees, and by SuccessiveLink, the function
    * which performs the main logic of meld, merges it into the existing
    * heap. It then finds the new minimum.
    *
    * Complexity: Aside from increasing the counter at O(1) and creating a new
    * node at O(1), the meaningful work is performed by SuccessiveLink at O(logn)
    * and findMinimumRoot at O(logn). Together, the complexity is O(logn)
    */
    public void insert(int value) 
    {
    	++size;
    	HeapNode node = new HeapNode(value);
    	if (rootListHead == null) {
    		rootListHead = node;
    		minimum = findMinimumRoot();
    		return;
    	}
    	SuccessiveLink(rootListHead,node,LinkArraySize( size ));
    	minimum = findMinimumRoot();
    }


    /**
     * private HeapNode findMinimumRoot()
     * 
     * precondition: none
     * postcondition: isHeap()
     * 
     * This function traverses the root list of tree-roots from beginning to end, and finds the node
     * with the minimum value.
     * Complexity: it works in O(number of trees), which is O(log n).
     * @return The root with the least value, or null if empty()
     */
    private HeapNode findMinimumRoot() {
    	if (empty())
    		return null;
    	
    	HeapNode i = rootListHead;
    	int tempValue = rootListHead.value;
    	HeapNode ret = i;
    	while (i != null) {
    		if (i.value < tempValue) {
    			tempValue = i.value;
    			ret = i;
    		}
    		i = i.nextSibling;
    	}
    	return ret;
    }
    
    
    /**
     * private HeapNode findMinimumRootAndRemoveFromRootList()
     * 
     * precondition: none
     * postcondition: Af L is the root list before calling the function,
     * 				  then $ret is min(L, key=lambda x: x.value).
     * 				  Also, $ret will not be in the root list anymore.
     * 				  if empty(), $ret = null.
     * 
     * This function traverses the root list until it finds the minimum root node,
     * and takes it out of the list by appending the root after it to the root before it.
     * 
     * Complexity: The function performs a fixed number of O(1) operations for every tree,
     * Therefore it is O(number of trees) which is O(log n).  
     * @return the same value as findMinimumRoot.
     */
    private HeapNode findMinimumRootAndRemoveFromRootList() {
    	if (empty())
    		return null;
    	
    	HeapNode i = rootListHead;
    	int tempValue = rootListHead.value;
    	HeapNode ret = i;
    	HeapNode previous = null;
    	HeapNode retPrevious = null;
    	while (i != null) {
    		if (i.value < tempValue) {
    			tempValue = i.value;
    			ret = i;
    			retPrevious = previous;
    		}
    		previous = i;
    		i = i.nextSibling;
    	}
    	if (retPrevious == null) { // the minimum node is the first in the list
    		rootListHead = ret.nextSibling; // actually, at this point, ret == rootListHead 
    	} else {
    		retPrevious.nextSibling = retPrevious.nextSibling.nextSibling;
    	}
    	return ret;
    }
    
    
    /**
    * public void deleteMin(int[] a, int heapsize)
    *
    * precondition: heapsize >= 1
    *               isHeap()
    * 
    * postcondition: isHeap()
    * 
    * This function follows the exact algorithm described in Cormen:
    * 1. take out the minimum root
    * 2. create a new heap
    * 3. append all level-one children of the minimum root to the new heap, in reverse order
    * 4. merge the new heap to $this, or if it is empty, simply find a new minimum.
    * 
    * Complexity: the call to findMinimumRootAndRemoveFromRootList is O(log n),
    * 	traversing all the children of a root is O(log n),
    * 	the meld() call is O(log n), 
    * 	or the findMinimumRoot() call is O(log n).
    * 	Overall: O(log n)
    * 
    */
    public void deleteMin()
    {
    	--size;
    	
    	HeapNode minimum = findMinimumRootAndRemoveFromRootList();
     	
    	Heap newHeap = new Heap();
    	HeapNode i = minimum.firstChild;
    	HeapNode next = null;
    	while (i != null) {
    		next = i.nextSibling;
    		if (i != null) {
    			i.nextSibling = newHeap.rootListHead;
    			newHeap.rootListHead = i;
    		}
    		i = next;
    	}
    	
    	//The call to .empty() is safe, seeing as empty simply compares pointers
    	if (!newHeap.empty()) {
    		meld(newHeap);
    	}
    	//if there's no heap to meld, just find a new minimum.
    	else
    	{
    		this.minimum = findMinimumRoot();
    	}
    }

	/**
	 * Calculates the size of the array needed for Successive-Linking
	 * a certain amount of elements. This is log_2(elements) + 1. This
	 * is the rank of the largest tree needed to store the elements.
	 * Precondition: elementCount > 0
	 * @param elementCount - the number of elements which will be in the
	 * heap at the end of the successive link
	 * @return log_2(elementCount) + 1
	 */
	private int LinkArraySize(int elementCount) {
    	//The number of successive link slots we need (w/ new size) is 
		return (int)Math.ceil(Math.log( elementCount )/Math.log(2)) + 1;
	}

    /**
     * public int getMin()
     *
     * precondition: heapsize >= 1
     *               isHeap()
     * 
     * postcondition: isHeap()
     * 
     * This function returns the minimum value in the heap. The data structure keeps a reference
     * to the minimum valued node that is updated whenever something changes.
     * 
     * Complexity: O(1).
     * @return The heap's minimum.
     */
    public int getMin()
    {
    	return minimum.value;
    } 
    
    /**
     * public void meld (Heap heap2)
     *
     * precondition: isHeap()
     * 		     heap2.isHeap()
     * 
     * postcondition: isHeap()
     * 		      heap2.getHeapsize=0;
     * 
     * The method will perform meld on this heap and heap2 into the current heap.
     * First, it computes the number of needed slots for the link, based on the
     * added size of both heaps, and then calls SuccessiveLink with both tree-lists
     * in order to merge them into one heap. Finally, it calls findMinimumRoot() to
     * update the pointer to the minimum.
     * 
     * Complexity: Two calls to getHeapsize() are O(1) apiece, as is LinkArraySize.
     * The two meaningful calls are SuccessiveLink at O(logn) and findMinimumRoot at
     * O(logn). Updating the size of both heaps and the head pointer at heap2 are all
     * at O(1), so the total complexity will be O(logn).
     *
     * @param heap2 - A heap to meld into this heap. Will be emptied out.
     */
    public void meld (Heap heap2)
    {
    	if (heap2.rootListHead == null) return;
    	if (rootListHead == null) {
    		rootListHead = heap2.rootListHead;
    		heap2.rootListHead = null;
    	}
    	//The number of successive link slots we need is 
    	int newSize = getHeapsize() + heap2.getHeapsize();
    	int arraySize = LinkArraySize(newSize);
    	
    	SuccessiveLink(rootListHead,heap2.rootListHead,arraySize);
    	
    	size = newSize;
    	
	heap2.rootListHead = null;
	heap2.size = 0;
	this.minimum = findMinimumRoot();
    	
    	
    }
    
    /**
      * Performs the "binary addition" of two lists, in the method
      * of 'Successive Linking' as was taught in class:
      * 1. An array is created, enough to fit all the elements, as calculated
      *    by LinkArraySize().
      * 2. The elements of the first list are placed into the array by rank
      *    (there is only one tree of any rank in the first heap/list)
      * 3. Next, the second list is iterated on. For each tree root in the list:
      *    3.1. If the array cell for the node's rank is null, it is placed there.
      *    3.2. Otherwise, it is linked with the tree whose node is in said cell.
      *    3.3. Once it has been linked, the "relink" flag is turned on, and the
      *         loop is repeated for that tree.
      * 4. Once the linking has taken place, the new trees, that are now again one
      *    of each rank, are linked into a new list and attached to the root.
      *
      * Complexity: Performs an iteration over the roots of both trees, which are
      * sized O(logn) each, and, then another iteration over the list of roots that
      * was created, which is sized *precisely* log_2(n) + 1 - Together, this is a
      * total of O(logn) for the function.
      *
      * @param myRootList - First list of heap trees
      * @param otherRootList - Second list of heap trees
      * @param linkSize - Size of trees list, calculated outside where the element
      * count is known.
      */
    private void SuccessiveLink(
		HeapNode myRootList, 
		HeapNode otherRootList, 
		int linkSize
    ) {
    	HeapNode [] linkList = new HeapNode[linkSize];
    	
    	HeapNode node = myRootList;
    	while (node != null) {
    		linkList[node.rank] = node;
    		node = node.nextSibling;
    	}
    	
    	node = otherRootList;
    	HeapNode nextNode = null;
    	boolean relink = false;
    	while (node != null) {
    		if (!relink) {
	    		//Funny thing happens here: you end up linking the node part of
	    		//the time and altering its next sibling. So we'll take hold of
	    		//it now, for safekeeping.
	    		nextNode = node.nextSibling;
    		}
    		else {
    			relink = false;
    		}
    		
    		if (linkList[node.rank] == null) {
    			linkList[node.rank] = node;
    		}
    		else{
    			HeapNode other = linkList[node.rank];
    			linkList[node.rank] = null;
    			if (node.value < other.value) {
    				node.addChild(other);
    				relink = true;
    				continue;
    			}
    			else {
    				other.addChild(node);
    				node = other;
    				relink = true;
    				continue;
    			}
    		}
    		
    		node = nextNode;
    	}
    	
    	//now we have one apiece of all nodes
    	//we want to link them into a tree (updating the
    	//new minimum will take place outside)
    	rootListHead = null;
    	for (int i = 0; i < linkList.length; ++i) {
    		if (linkList[i] != null) {
    			if (rootListHead == null) {
    				rootListHead = linkList[i];
    				rootListHead.nextSibling = null;
    			}
    			else {
    				linkList[i].nextSibling = rootListHead.nextSibling;
    				rootListHead.nextSibling = linkList[i];
    			}
    		}
    	}
    }
    
    /**
    * public boolean contains(int i)
    *
    * precondition: isHeap()
    * 
    * The method returns true if and only if the heap
    * contains an element of value i.
    *
    * This method iterates over all tree roots in the linked list
    * and calls the recursive contains() method of HeapNode for each
    * of them. If any of them returns true, it will stop the search
    * and return true.
    *
    * Complexity: Let us assume the n elements of the heap are divided into
    * k trees sized n_1 + n_2 + ... + n_k = n.
    * For each of the k trees, HeapNode's contains will be called at O(n_i).
    * For the worst case, in which the element is not found, the iteration will
    * run all k trees at O(n_1 + n_2 + ... + n_k) = O(n).
    *
    * @param i - The integer to search.   
    */
	public boolean contains(int i){
		HeapNode node = rootListHead;
		while (node != null) {
			if (node.Contains(i)) {
				return true;
			}
			node = node.nextSibling;
		}
		
		return false;
    }
	
	/**
	 * public String toString()
	 * 
	 * Returns a string representation of the entire heap. It uses HeapNode.toString. 
	 * The representation is ( root1 | root2 | root 3 ...) and each root's representation is
	 * the value returned from HeapNode.toString.
	 * 
	 *  Example: ( \<68\>) | (((505)399) (390) \<102\>) | ((318) \<97\>)
	 *  
	 *  Complexity: Assuming String concatenation works in O(size of final string),
	 *  This function is O(n) since it causes a chain of size() recursive calls, node.toString()
	 *  is called for each node. O(n)
	 */
	public String toString() {
		if (empty())
			return "()";
		String s = "";
		// iterate over roots
		HeapNode n = rootListHead;
		while (n != null) {
			s += n.toString();
			s += " | ";
			n = n.nextSibling;
		}
		return s.substring(0, s.length() - 3);
	}
	
    /**
     * public class HeapNode
     * 
     * Class for a single node in a tree of the heap. Being a recursive
     * structure by design, each node points to a parent, the next sibling
     * in the same level in the same tree, and its first child (which, in
     * turn points to the next children in a linked list.)
     *  
     */
    public class HeapNode{
    	private HeapNode parent, firstChild, nextSibling;
    	private int value, rank = 0;
    	
    	HeapNode(int value) {
    		this.value = value;
    	}
    	
    	
    	
    	/**
    	 * public void addChild(HeapNode other)
    	 * 
    	 * Adds a child to the current node.
    	 * @param other - the node to be made child of $this.
    	 * 
    	 * Complexity: performs four basic operations. O(1).
    	 */
    	public void addChild(HeapNode other) {
			rank++;
			other.parent = this;
			other.nextSibling = this.firstChild;
			this.firstChild = other;
		}

	/**
	 * private boolean isHeap(int x)
	 * 
    	 * Recursive check of the three conditions:
    	 * 1. No element in any of the trees is larger than either of its sons.
	 * 2. Every tree is a legal binomial tree.
	 * 3. there are no 2 trees of the same degree.
	 * 
	 * Complexity: This function is recursively called for every node in the subtree
	 * 	whose root is $this, and it performs a fixed number of operations. Therefore its
	 * 	Complexity is O(n).
	 * 
    	 * @return true iff the node represents the root of a valid heap
    	 */
    	private boolean isHeap() {
    		//Check against parent (#1)
    		if ((parent != null) && (parent.value > this.value)) {
    			return false;
    		}
    		
		boolean[] trees = new boolean[this.rank + 1];
    		HeapNode child = this.firstChild;
    		while (child != null) {
    			//mark rank (#3)
			if (trees[ child.rank]) {
				return false;
			}
			else {
				trees[child.rank] = true;
			}
    			
    			//check heap correctness (#2)
    			if (!child.isHeap()) {
    				return false;
    			}
    			
    			child = child.nextSibling;
    		}
    		
    		return true;
    	}
    	
    	/**
    	 * private boolean Contains(int x)
    	 * 
    	 * precondition: isHeap()
    	 * postcondition: isHeap()
    	 * 
    	 * This function searches for the value x in the heap. It simply traverses the trees
    	 * recursively and looks for the given value.
    	 * 
    	 * Complexity: O(n), as it passes precisely once through each node.
    	 * 
    	 * @param x - the value t be searched in the heap.
    	 * @return whether the heap contains a node whose value is x.
    	 */
    	private boolean Contains(int x) {
    		if (this.value == x) {
    			return true;
    		}
    		
    		HeapNode child = this.firstChild;
    		while (child != null) {
    			if (child.Contains(x)) {
    				return true;
    			}
    			
    			child = child.nextSibling;
    		}
    		
    		return false;
    	}
    	
    	/**
    	 * public String toString()
    	 * 
    	 * This function returns a string representation of the subtree rooted at the node object $this.
    	 * a single node is represented (child1 child2 ... $value). A root node in the heap is
    	 * represented (child1 child2 ... \<$value\>).
    	 * 
    	 * For example, a 3-level binomial tree is represented (((505)399) (390) \<102\>).
    	 * 
    	 * Complexity: assuming string operations are, totally, O(size of resulting string),
    	 * 	the complexity is O(number of trees in the subtree).
    	 */
    	@Override
    	public String toString() {
    		if (rank == 0 && parent != null) {
    			return "(" + value + ")";
    		}
    		String s = "(";
    		HeapNode n = firstChild;
    		for (int i = 0; i < rank; i++) { // for each child node
    			s += n.toString();
    			n = n.nextSibling;
    			if (i != rank - 1)
    				s += " ";
    		}
    		if (parent == null) {
    			s += " <" + value + ">)";
    		} else {
    		s += value + ")";
    		}
    		
    		return s;
    	}
    }
}
